#ifndef _CRT_AVL_H
#define _CRT_AVL_H

#include <crt_core.hpp>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct avl_tree avl_tree_t;
typedef struct avl_node avl_node_t;
typedef uintptr_t avl_index_t;

#ifndef __LP64__

struct avl_node {
    struct avl_node* avl_child[2];
    struct avl_node* avl_parent;
    unsigned short avl_child_index;
    short avl_balance;
};

#define AVL_XPARENT(n)      ((n)->avl_parent)
#define AVL_SETPARENT(n, p) ((n)->avl_parent = (p))

#define AVL_XCHILD(n)      ((n)->avl_child_index)
#define AVL_SETCHILD(n, c) ((n)->avl_child_index = (unsigned short)(c))

#define AVL_XBALANCE(n)      ((n)->avl_balance)
#define AVL_SETBALANCE(n, b) ((n)->avl_balance = (short)(b))

#else

struct avl_node {
    struct avl_node* avl_child[2];
    uintptr_t avl_pcb;
};

#define AVL_XPARENT(n)      ((struct avl_node*)((n)->avl_pcb & ~7))
#define AVL_SETPARENT(n, p) ((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))

#define AVL_XCHILD(n)      (((n)->avl_pcb >> 2) & 1)
#define AVL_SETCHILD(n, c) ((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2)))

#define AVL_XBALANCE(n)      ((int)(((n)->avl_pcb & 3) - 1))
#define AVL_SETBALANCE(n, b) ((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1))))

#endif

#define AVL_NODE2DATA(n, o) ((void*)((uintptr_t)(n) - (o)))
#define AVL_DATA2NODE(d, o) ((struct avl_node*)((uintptr_t)(d) + (o)))

#define AVL_INDEX2NODE(x)  ((avl_node_t*)((x) & ~1))
#define AVL_INDEX2CHILD(x) ((x)&1)
#define AVL_MKINDEX(n, c)  ((avl_index_t)(n) | (c))

struct avl_tree {
    struct avl_node* avl_root;
    int (*avl_compar)(const void*, const void*);
    size_t avl_offset;
    unsigned long avl_numnodes;
    size_t avl_size;
};

#define AVL_BEFORE (0)
#define AVL_AFTER  (1)

void avl_create(avl_tree_t* tree, int (*compar)(const void*, const void*), size_t size, size_t offset);

void* avl_find(avl_tree_t* tree, void* node, avl_index_t* where);

void avl_insert(avl_tree_t* tree, void* node, avl_index_t where);

void avl_insert_here(avl_tree_t* tree, void* new_data, void* here, int direction);

void* avl_first(avl_tree_t* tree);
void* avl_last(avl_tree_t* tree);

#define AVL_NEXT(tree, node) avl_walk(tree, node, AVL_AFTER)
#define AVL_PREV(tree, node) avl_walk(tree, node, AVL_BEFORE)

void* avl_nearest(avl_tree_t* tree, avl_index_t where, int direction);

void avl_add(avl_tree_t* tree, void* node);
void avl_remove(avl_tree_t* tree, void* node);

int avl_update(avl_tree_t*, void*);
int avl_update_lt(avl_tree_t*, void*);
int avl_update_gt(avl_tree_t*, void*);

unsigned long avl_numnodes(avl_tree_t* tree);
int avl_is_empty(avl_tree_t* tree);

void* avl_destroy_nodes(avl_tree_t* tree, void** cookie);

void avl_destroy(avl_tree_t* tree);

#ifdef __cplusplus
}
#endif

#endif
